package leetcode.code2048;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;

public class Solution implements IDebug {

	public int nextBeautifulNumber1(int n) {
		for (int i = n + 1; i < Integer.MAX_VALUE; i++) {
			int num = i;
			int[] d = new int[10];
			while (num > 0) {
				int last = num % 10;
				d[last] += 1;
				num /= 10;
			}
			boolean ok = true;
			for (int j = 0; j < d.length; j++) {
				if (d[j] != 0 && d[j] != j) {
					ok = false;
					break;
				}
			}
			if (ok) {
				return i;
			}
		}
		return 0;
	}

	public void table() {
		List<Integer> table = new ArrayList<Integer>();
		for (int i = 1; i < Integer.MAX_VALUE; i++) {
			int num = i;
			int[] d = new int[10];
			while (num > 0) {
				int last = num % 10;
				d[last] += 1;
				num /= 10;
			}
			boolean ok = true;
			for (int j = 0; j < d.length; j++) {
				if (d[j] != 0 && d[j] != j) {
					ok = false;
					break;
				}
			}
			if (ok) {
				table.add(i);
			}
		}
		Integer[] nums = (Integer[]) table.toArray();
	}

	static Integer[] nums;

	static {
		List<Integer> table = new ArrayList<Integer>();
		for (int i = 1; i < Integer.MAX_VALUE; i++) {
			int num = i;
			int[] d = new int[10];
			while (num > 0) {
				int last = num % 10;
				d[last] += 1;
				num /= 10;
			}
			boolean ok = true;
			for (int j = 0; j < d.length; j++) {
				if (d[j] != 0 && d[j] != j) {
					ok = false;
					break;
				}
			}
			if (ok) {
				table.add(i);
			}
		}
		nums = (Integer[]) table.toArray();
	}

	public int nextBeautifulNumber(int n) {
		int l = 0, r = nums.length - 1;
		int ans = 0;
		while (l <= r) {
			int m = ((r - l) >> 1) + l;
			if (nums[m] > n) {
				ans = nums[m];
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		this.nextBeautifulNumber(1224443);

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
